[% setvar title Keyed arrays %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Keyed arrays</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Glenn Linderman &lt;<a href='mailto:glenn@linderman.com'>glenn@linderman.com</a>&gt;
  Date: 20 Sep 2000
  Last Modified: 28 Sep 2000
  Mailing List: <a href='mailto:perl6-language@perl.org'>perl6-language@perl.org</a>
  Number: 268
  Version: 3
  Status: Withdrawn</pre>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>The  idea here  is to  merge the  concepts of  array and  hash,  not to
replace  either  one, but  to  provide  some  middle ground  with  data
structures  having some  characteristics of  each.  The  resultant data
structure is  based on array,  may be more  costly than hash,  for some
operations, may be more efficient  than hashes for some operations, and
may provide a more compatible  solution for some types of problems than
other RFCs.</p>
<a name='Notes on withdrawal'></a><h1>Notes on withdrawal</h1>
<p>There are some  nice ideas in here, if only they  could work.  At least
it provided  a bit  of inspiration for  RFC 273,  so it wasn't  a total
waste of time.</p>
<a name='CHANGES'></a><h1>CHANGES</h1>
<p>In Version 2:</p>
<p>Clarify wording  in various  places.  Prohibit use  of splice  on keyed
arrays that  actually contain keys.   Change the default array  type to
:nokey, since splice is prohibited on keyed arrays.</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>These  are not  pseudo-hashes.   Michael Schwern,  author  of RFC  241:
Pseudo-hashes must die! after some lengthy discussion, said: &lt;quote&gt; Ya
know, I'm going to say that $aref-&gt;[string] might be made to work where
pseudo-hashes failed. &lt;/quote&gt;.  However,  that is not intended to mean
that  Mr.   Schwern  endorses this  proposal,  but  I  did take  it  as
encouragement to develop this RFC  to squeak in before the deadline and
hope that it lends just a bit credence to the proposal.  That said...</p>
<p>I think  that Mr.  Schwern's comment  does imply that  a proposal along
these lines  might be  able to solve  problems that  pseudo-hashes were
invented  to  solve,  in  ways  that might  be  less  problematical  to
implement; this would  allow pseudo-hashes to not need  to coexist with
keyed arrays,  so the proposal  doesn't discuss such  coexistance.  See
also RFC 241.</p>
<a name='Definition syntax'></a><h2>Definition syntax</h2>
<p>An array could have an optional namespace.  Probably best to call these
keys, because  it really is the  same concept as hash  keys--we look up
values  using  them.   Probably  there  could be  several  flavors,  as
described below.  I'm not yet  certain if all these flavors are useful,
or  if  all these  flavors,  even  if useful,  are  worth  the pain  of
implementation, since  I don't know the cost  of implementation.  There
may  be  flavors  I  haven't  thought  of  yet,  that  would  be  worth
implementing.  All  but the first are generically  called keyed arrays.
Here's my current concept list:</p>
<pre>    my/our @array :nokey;
    my/our @array :key;
    my/our @array :initialkey ( key0, key1, ... );
    my/our @array :keyonly;
    my/our @array :hashsyntax;</pre>
<p>With the :nokey attribute, we  would have a familiar perl&lt;6 array.  Use
numeric indexes, and [] indexing syntax.  This would be the default, if
no attribute is specified, for compatibility.</p>
<p>With the  :key attribute,  it would be  allowed, but not  required, for
keys  to be  added  to  point to  particular  array elements.   Numeric
indexing could still  be used for speed.  Not  all array elements would
necessarily have keys.</p>
<p>The :initialkey  variation would  specify in the  definition a  list of
keys which  would correlate  to the  array indexes 0,  1, ...</p>
<p>The :keyonly variation  would be less efficient, and  would require use
of keys for lookup.  Of course, the compiler could translate fixed keys
into numeric indexes under the covers for performance.</p>
<p>The  :hashsyntax  variation is  identical  to  the :keyonly  variation,
except for  the syntax,  which is like  hashes instead of  like arrays.
This  variation  could  unify  the  concepts of  hash  and  array.  The
definition  of a :hashsyntax  array should  probably reserve  a special
pointer in the  symbol table so that the similarly  named hash would be
automatically  defined for  access,  but would  actually  refer to  the
:hashsyntax keyed array.  In other words, the definition of</p>
<pre>    my/our @array :hashsyntax;</pre>
<p>would hide the definition of %array in the same way that</p>
<pre>    my/our %array</pre>
<p>would  hide a  prior definition  of %array.   And references  to %array
would thenceforth actually be references to the keyed array @array.</p>
<a name='Reference syntax'></a><h2>Reference syntax</h2>
<p>The syntaxes</p>
<pre>    $foo['element']
    $foo[element]</pre>
<p>or for :hashsyntax arrays, either the above or</p>
<pre>    $foo{'element'}
    $foo{element}</pre>
<p>would be interpreted as a reference to @foo.  If the namespace for @foo
contains 'element', that member of  @foo is the interpretation.  If the
namespace for @foo does not  contain 'element', then 'element' is added
to the namespace for @foo, the size  of @foo is increased by 1, and the
member 'element' refers to the newly added item in @foo.</p>
<p>So, starting with</p>
<pre>   my @foo:key; # empty array
   $foo ['month'] = 10;  #  $#foo == 1, $foo[0] == 10
   $foo ['day'] = 20;   # $#foo == 2, $foo [1] == 20
   $foo ['year'] = 30;   # $#foo = 3, $foo [2] == 30</pre>
<p>We achieve an array with 3 elements.  There is a clear parallel between
this and</p>
<pre>   my %foo;
   $foo{'month'} = 10;
   $foo{'day'} = 20;
   $foo{'year'} = 30;</pre>
<p>However, the lookups for @foo are done at compile time, the lookups for
%foo are done at runtime.</p>
<p>For :key and :initialkey arrays, the syntax</p>
<pre>    $foo[$bar]</pre>
<p>would inspect $bar to determine if it is convertable to numeric.  If it
is, the value is used as the numeric index of the array.  If it is not,
it is treated as a key for the array, and is looked up in the namespace
of the array.</p>
<p>For :keyonly and  :hashsyntax arrays, all indexes are  considered to be
string keys just  like hash keys, requiring lookup  in the namespace of
the array.</p>
<p>Perl uses some heuristic to decide  whether a bareword within the {} of
a hash  key reference  is a  function or a  string, the  same heuristic
should be applied within [] for keyed arrays.</p>
<p>Push,  pop,  shift,  and  unshift   are  not  valid  for  :keyonly  and
:hashsyntax  arrays,  because  they  access  data by  index,  which  is
prohibited for  those types of  keyed arrays.  Splice is  prohibited on
all keyed arrays, to allow compile time name lookup.</p>
<p>The  operations keys,  values,  and  each would  make  sense for  keyed
arrays.   Their syntax  should be  extended to  accept keyed  arrays as
parameters, and the semantics should be similar to that for hashes.  It
should be  noted that values is  not necessarily the same  order as the
original keyed  array, since it would  iterate via the  keys.  For :key
and :initialkey arrays,  it would not even necessarily  be the complete
array, because not all array entries would necessarily have keys.</p>
<a name='Usages'></a><h2>Usages</h2>
<a name='Garrulous builtins'></a><h3>Garrulous builtins</h3>
<p>(I cloned this heading from RFC  259, thanks Damian) (I cloned the list
of  functions  from  RFC 37,  thanks  Jarkko)  (I  cloned the  list  of
standardized key names from RFC 259, thanks again, Damian)</p>
<p>The idea here is that some functions return an array of values that are
hard to keep  track of.  It would be nice  to retain compatibility, but
also be  able to access the members  of the array by  name, rather than
number.  Since these arrays are of fixed size, and known values, we can
apply  the :initialkeys  variation to  these functions.   The functions
remain  fully compatible with  current definitions  and usage  of their
results, however, new code could  be written using the names instead of
the numbers  to access the results.   One example, and  then the cloned
lists of details.</p>
<pre>   my ( @stat_array ) = stat ( $filename );
   print &quot;File $filename has a size of $stat_array[size] bytes.\n&quot;;</pre>
<a name='List of garrulous builtins'></a><h4>List of garrulous builtins</h4>
<pre>        caller [1]
        getgrent
        getgrnam
        getgrgid
        gethostbyaddr
        gethostbyname
        gethostent
        getnetbyaddr
        getnetbyname
        getnetent
        getprotobyname
        getprotobynumber
        getprotoent
        getpwent
        getpwnam
        getpwuid
        getservbyname
        getservbyport
        getservent
        gmtime
        localtime
        stat</pre>
<p>Some changes to this list may be necessitated by other changes to Perl6.</p>
<a name='Standardized keys'></a><h4>Standardized keys</h4>
<p>The standardized keys for these functions would be:</p>
<ul>
<li><a name='stat/lstat'></a><code>stat</code>/<code>lstat</code></li>
<pre>                'dev'           Device number of filesystem
                'ino'           Inode number
                'mode'          File mode  (type and permissions)
                'nlink'         Number of (hard) links to the file
                'uid'           Numeric user ID of file's owner
                'gid'           Numeric group ID of file's owner
                'rdev'          The device identifier (special files
only)
                'size'          Total size of file, in bytes
                'atime'         Last access time in seconds since the
epoch
                'mtime'         Last modify time in seconds since the
epoch
                'ctime'         Inode change time in seconds since the
epoch
                'blksize'       Preferred block size for file system I/O

                'blocks'        Actual number of blocks allocated</pre>
<li><a name='localtime/gmtime'></a><code>localtime</code>/<code>gmtime</code></li>
<pre>                'sec'           Second
                'min'           Minute
                'hour'          Hour
                'mon'           Month
                'year'          Year
                'mday'          Day of the month
                'wday'          Day of the week
                'yday'          Day of the year
                'isdst'         Is daylight savings time in effect
                                (localtime only)</pre>
<li><a name='caller'></a><code>caller</code></li>
<pre>                'package'       Name of the package from which sub was
called
                'file'          Name of the file from which sub was
called
                'line'          Line in the file from which sub was
called
                'sub'           Name by which sub was called
                'args'          Was sub called with args?
                'want'          Hash of values returned by want()
                'eval'          Text of EXPR within eval EXPR
                'req'           Was sub called from a C&lt;require&gt; (or
C&lt;use&gt;)?
                'hints'         Pragmatic hints with which sub was
compiled
                'bitmask'       Bitmask with which sub was compiled</pre>
<li><a name='getpw*'></a><code>getpw*</code></li>
<pre>                'name'          Username
                'passwd'        Crypted password
                'uid'           User ID
                'gid'           Group ID
                'quota'         Disk quota
                'comment'       Administrative comments
                'gcos'          User information
                'dir'           Home directory
                'shell'         Native shell
                'expire'        Expiry date of account of password</pre>
<li><a name='getgr*'></a><code>getgr*</code></li>
<pre>                'name'          Group name
                'passwd'        Group password
                'gid'           Group id
                'members'       Group members</pre>
<li><a name='gethost*'></a><code>gethost*</code></li>
<pre>                'name'          Official host name
                'aliases'       Other host names
                'addrtype'      Host address type
                'length'        Length of address
                'addrs'         Anonymous array of raw addresses in 'C4'
format</pre>
<li><a name='getnet*'></a><code>getnet*</code></li>
<pre>                'name'          Official name of netwwork
                'aliases'       Other names for network
                'addrtype'      Type of network number
                'net'           Network number</pre>
<li><a name='getproto*'></a><code>getproto*</code></li>
<pre>                'name'          Official name of protocol
                'aliases'       Other names for protocol
                'proto'         Protocol number</pre>
<li><a name='getserv*'></a><code>getserv*</code></li>
<pre>                'name'          Official name of service
                'aliases'       Other names for service
                'port'          Port at which service resides
                'proto'         Protocol to be used</pre>
<a name='Accessor functions'></a><h3>Accessor functions</h3>
<p>The :keyonly and :hashsyntax variation would allow objects built out of
keyed arrays to  use (multiple) inheritance, within the  set of objects
built out of keyed arrays, of course.  It seems hard (to me) to inherit
from an object that is a hash  for an object that is an array, and vice
versa.   If the  unified  :hashsyntax variation  is implementable,  one
could easily  convert (with  a pragma?) existing  objects to  use keyed
arrays instead of hashes, and thus gain any benefits for accessor speed
as noted next.</p>
<p>For objects  built out of  them, and if  such objects implement  a fair
number of accessor  function (see RFC 163) which  are effectively fixed
value keyed  lookup and store operations, the  compiler could translate
the fixed key  values in the accessor functions  to an index internally
for speed.</p>
<a name='Pairs'></a><h3>Pairs</h3>
<p>I'm not  yet sure  how this  RFC would interact  with RFC  84.  Clearly
there would be some ramifications, however, should both be adopted.</p>
<a name='Sets'></a><h3>Sets</h3>
<p>I'm not  yet sure how  this RFC would  interact with RFC  179.  Clearly
there could be some ramifications, however, should both be adopted.</p>
<a name='Private/public'></a><h3>Private/public</h3>
<p>RFC 188 should  interact with this RFC, if both are  adopted.  I see no
conflict to  extending RFC 188 to  use its keywords  with keyed arrays,
with the same semantics on the names.</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>One possible  implementation of a  keyed array would  be to add  to the
usual array implementation a name table  via a hidden hash and a hidden
numeric value, called the offset, which is initially zero.</p>
<p>The purpose  of the name  table is to  provide the lookup from  name to
number.   For   each  object,  the  name  table   would  contain  (key,
index-base)  pairs  that would  provide  the  translation  from key  to
index-base.  Index-base  is added to  offset to produce the  index into
the array.</p>
<p>The purpose  of the offset  is to be  added to the number  that results
from a  key-to-index translation before you actually  lookup the value.
This  allows operations  such as  shift and  unshift, which  affect the
relationship of all  indexes and data values to  be implemented without
updating each  entry in the name  table.  If a later  lookup returns an
index less  than zero, an undef  is returned.  So  shift would decrease
offset by  the shift  count, and unshift  would increase offset  by the
shift count.  (The shift count is always 1 in perl&lt;6, but see RFC 56.)</p>
<p>With the above in mind, the  algorithm for inserting a new entry in the
name table, would be to create  a pair consisting of (key, $# - offset)
and insert it into the name table for the keyed array.</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>RFC 21: Subroutines: Replace <code>wantarray</code> with a generic <code>want</code> function</p>
<p>RFC 37: Positional Return Lists Considered Harmful</p>
<p>RFC 56: Optional 2nd argument to <code>pop()</code> and <code>shift()</code></p>
<p>RFC 84: Replace =&gt; (stringifying comma) with =&gt; (pair constructor)</p>
<p>RFC 127: Sane resolution to large function returns</p>
<p>RFC 163: Objects: Autoaccessors for object data structures</p>
<p>RFC 179: More functions from set theory to manipulate arrays</p>
<p>RFC 188: Objects : Private keys and methods</p>
<p>RFC 241: Pseudo-hashes must die!</p>
<p>RFC 259: Builtins : Make use of hashref context for garrulous builtins</p>
</div>
